package backTrack;

public class ds37_sudoku {
    public static void main(String[] args) {
        char[][] ch = new char[][]{{'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
        solveSudoku(ch);
    }

    public static void solveSudoku(char[][] board) {
        dfs(board);
    }
    public static boolean dfs(char[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if(board[i][j] == '.'){
                    for (int k = 1; k <= 9; k++) {
                        if(isValid(board, (char) (k + '0'), i, j)){
                            board[i][j] = (char) (k + '0');
                            if(dfs(board))
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isValid(char[][] board, char c, int i, int j){
        for (int k = 0; k < 9; k++) {
            if(board[i][k] == c)
                return false;
        }
        for (int k = 0; k < 9; k++) {
            if(board[k][j] == c)
                return false;
        }
        for (int k = 3 * (i / 3); k < 3 * (i / 3) + 3; k++) {
            for (int l = 3 * (j / 3); l < 3 * (j / 3) + 3 ; l++) {
                if(board[k][l] == c)
                    return false;
            }
        }
        return true;
    }

}
